A computer aided design (CAD) flow includes a synthesis stage, a partition or clustering stage, and a place and route stage. During the synthesis stage, a register transfer layer (RTL) description is converted into an unoptimized flattened netlist of basic gates. Moreover, logic optimization is performed on the flattened netlist to simplify and remove duplicate logic. The optimized netlist is then mapped to a specific target technology using a library of basic building blocks.
An output of the synthesis stage is a flattened netlist of basic building blocks such as logic gates and registers specific to a target technology. The flattened netlist can be upwards of millions of elements. Providing such large flattened netlists directly into the placement and route stage reduces the probability that the placement and route stage will be able to find a good solution for routability and timing or, at the very least, it would take an exceedingly long time to do so.
Typically the clustering or partitioning stage is performed prior to the placement stage to coarsen the flattened netlist in order to make the flattened netlist more manageable for placement to produce better quality solutions in less time.
There exist techniques which attempt to provide quick global information during these early stages in the CAD flow. For example, some of these techniques include using high-level partitioning or performing quick placements prior to the clustering stage.
However, these stages perform local optimizations with no insight on how these optimizations affect a final design implementation of an integrated circuit. The synthesis and partitioning or clustering stages may make modifications to the flattened netlist based on what looks like good local information but which ultimately makes the placement and routing solution worse.
A problem with some of the existing techniques is that they themselves operate on the entire flattened netlist and thus dramatically increase compilation time. Also, because some of these existing techniques are meant to run quickly, they often get caught in a local minima.